package _17_剑指Offer;

public class _10_剑指Offer青蛙跳台阶问题 {


    public static void main(String[] args) {
        _10_剑指Offer青蛙跳台阶问题 v = new _10_剑指Offer青蛙跳台阶问题();

        System.out.println(v.numWays(100));
    }

    public int numWays(int n) {
        if (n <= 1) return 1;
        int first = 1;
        int second = 1;
        while (n-- > 1) {
            second = first + second;
            first = second - first;
            second %= 1000000007;
        }
        return second;
    }

    // 递归 (存在子问题的重复解，会出现超时问题)
    public int numWays1(int n) {
        if (n <= 1) return 1;

        return numWays(n - 1) + numWays(n - 2);
    }

}
